// https://leetcode.cn/problems/find-k-closest-elements/submissions/558820725/

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int l = 0, r = k-1;
        int p1 = 0, p2 = k-1;

        int n = arr.size();
        
        //从题中容易知道，窗口的大小是固定的，即k
        //如何判断这个子数组接近x? 求和比较即可

        int sum = 0;

        //先对窗口做一次求和
        for (int i = 0; i <= r; i++) sum += abs(x - arr[i]); 

        while (r < n) {
            r++;
            if (r >= n)
                break;

            //减去前面一个的差值，再加上后面一个的差值，得到新的和
            int sub = sum - abs(x - arr[r-k]) + abs(x - arr[r]);   
            if (sub < sum) {
                l = r-k+1; //左指针需要向后, 所以+1
                p1 = l, p2 = r;
            }
        }
        
        vector<int> ans;
        for (int i = p1; i <= p2; i++) {
            ans.push_back(arr[i]);
        }
        return ans;
    }
};